/*
https://leetcode-cn.com/problems/remove-boxes/solution/yi-chu-he-zi-by-leetcode-solution/
 */
public class Solution546 {

    int[][][] dp;

    public int removeBoxes(int[] boxes) {
        dp=new int[boxes.length][boxes.length][boxes.length];
        return cal(boxes,0,boxes.length-1,0);
    }

    private int cal(int[] boxes,int l, int r, int k) {
        if (l>r){
            return 0;
        }
        if (dp[l][r][k]==0){
            dp[l][r][k]=cal(boxes,l,r-1,0)+(k+1)*(k+1);
            for (int i=l;i<r;i++){
                if (boxes[i]==boxes[r]){
                    dp[l][r][k]=Math.max(dp[l][r][k],cal(boxes,l,i,k+1)+cal(boxes,i+1,r-1,0));
                }
            }
        }
        return dp[l][r][k];
    }

    public static void main(String[] args) {
        System.out.println(new Solution546().removeBoxes(new int[]{1,3,2,2,2,3,4,3,1}));
    }
}
